#include <stdio.h>  
#include <stdlib.h>

#define getRandom() \
    random() % 100
 
struct LinkList *merge(struct LinkList *first,struct LinkList *second);      
void printLinkList(struct LinkList *list);  
struct LinkList *mergeSort(struct LinkList *head);  
void destroyList(struct LinkList *list);

struct LinkList{  
    struct LinkList *next;  
    int value;  
} *linkList,node;  
  
int main()
{
    //build a linkList,end with an NULL node  
    srand(time(0));
    struct LinkList *list=(struct LinkList *)malloc(sizeof(node));  
    struct LinkList *current=list;  
    int i;
    struct LinkList *temp; 
    for(i=0;i<20;i++){  
        temp=(struct LinkList *)malloc(sizeof(node));  
        /*temp->value=getRandom();  */
        temp->value=random() % 100;
        current->next=temp;  
        current=current->next;  
    }  
    current->next=NULL;  

    printf("Before sort:\n");  
    printLinkList(list->next);  
      
    //mergeSort the list.  
    list = mergeSort(list->next);  
    printf("After sort:\n");  
    printLinkList(list);  

    destroyList(list);

    return 0;  
}  
  
/* 
  Mergesort the linkList. 
*/  
struct LinkList *mergeSort(struct LinkList *head)
{  
   struct LinkList *first;  
   struct LinkList *second;  
   first=head;  
   second=head;  
   if(first==NULL||first->next==NULL){  
       //Note here is the place that can jump out of the recursion.  
       return first;  
   }  
     
   //cut the LinkList into 2 list,one lead by "first",the other lead by "second".  
   while(second->next!=NULL && second->next->next!=NULL){  
       first=first->next;  
       second=second->next->next;  
   }  
   if(first->next!=NULL){  
       second=first->next;  
       first->next=NULL;  
       first=head;  
   }   
     
   //merge the List.  
   return merge(mergeSort(first),mergeSort(second));  
}  
  
/* 
  Merge the list. 
  It is quite similar with the operation of the merge of Array, 
  but note that because of the linklist,we avoid the large space expence of the  
  usual merge of array. 
*/  
struct LinkList *merge(struct LinkList *first,struct LinkList *second)
{      
    struct LinkList *resList; //=(struct LinkList *)malloc(sizeof(node)); 
    struct LinkList *current;  
    if (first->value < second->value) {
        current = first;
        first = first->next;
    } else {
        current = second;
        second = second->next;
    }
    resList = current;
      
    while(first!=NULL && second!=NULL){  
        if(first->value<=second->value){  
            current->next=first;
            first=first->next;  
            current=current->next;                             
        }else{  
            current->next=second;  
            second=second->next;            
            current=current->next;                              
        }  
    }  
      
    while(first!=NULL){  
        current->next=first;   
        current=current->next;                              
        first=first->next;  
    }
    while(second!=NULL){  
        current->next=second;    
        current=current->next;                             
        second=second->next;                    
    }
      
    return resList;
}  
  
/* 
  Print the LinkList. 
*/  
void printLinkList(struct LinkList *list){  
    while(list!=NULL){  
        printf("%d ",list->value);  
        list=list->next;  
    }  
    printf("\n");
}  

/*
 *Free the mem.
 */
void destroyList(struct LinkList *list)
{
    struct Linklist *tmp;
    while (list) {
        tmp = list->next;
        free(list);
        list = tmp;
    }
    
}
